package mao.leetcode.dp.leetcode120;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    /*
    1.先想清楚在写代码，注重画图。
    2.巧设计初始条件，简化判断。
    3.转化思路，寻找不一样的推导条件。
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> minPath = new ArrayList<>();
        for (List<Integer> list : triangle) {
            if (list.size() == 1) minPath.add(0);  //先进行补齐操作。
            else minPath.add(Integer.MAX_VALUE);

            for (int i = list.size()-1; i >=0; i--) {
                if (i==0) minPath.set(0,list.get(0)+minPath.get(0));
                else minPath.set(i, Math.min(minPath.get(i-1),minPath.get(i))+list.get(i));
            }
            //  minPath.add(minPath.get(minPath.size()-1)+list.get(list.size()-1));
        }
        int min=minPath.get(0);
        for (Integer integer : minPath) {
            if (integer<min) min=integer;
        }
        return min;
    }
}
